// 给定一个三角形 triangle ，找出自顶向下的最小路径和。
// 每一步只能移动到下一行中相邻的结点上。
// 相邻的结点 在这里指的是 下标 与 上一层结点下标 相同
// 或者等于 上一层结点下标 + 1 的两个结点。
// 也就是说，如果正位于当前行的下标 i ，
// 那么下一步可以移动到下一行的下标 i 或 i + 1 。
// 来源：力扣（LeetCode）
// 链接：https://leetcode.cn/problems/triangle
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function (triangle) {
  const len = triangle.length
  const dp = new Array(len).fill(0).map(() => new Array(len).fill(Infinity))
  dp[0][0] = triangle[0][0]

  for (let i = 1; i < len; i++) {
    dp[i][0] = dp[i - 1][0] + triangle[i][0]
  }
  for (let i = 0; i < len; i++) {
    for (let j = 1; j <= i; j++) {
      dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]
    }
  }

  return Math.min(...dp[len - 1])
}

console.log(
  minimumTotal([[-10]])
)














